//假设你有两个数组，一个长一个短，短的元素均不相同。找到长数组中包含短数组所有的元素的最短子数组，其出现顺序无关紧要。 
//
// 返回最短子数组的左端点和右端点，如有多个满足条件的子数组，返回左端点最小的一个。若不存在，返回空数组。 
//
// 示例 1： 
//
// 
//输入：
//big = [7,5,9,0,2,1,3,5,7,9,1,1,5,8,8,9,7]
//small = [1,5,9]
//输出：[7,10] 
//
// 示例 2： 
//
// 
//输入：
//big = [1,2,3]
//small = [4]
//输出：[] 
//
// 提示： 
//
// 
// big.length <= 100000 
// 1 <= small.length <= 100000 
// 
//
// Related Topics 数组 哈希表 滑动窗口 👍 77 👎 0


package LeetCode.editor.cn;

import java.util.HashMap;
import java.util.Map;

/**
 * @author ldltd
 * @date 2025-09-21 17:37:21
 * @description 面试题 17.18.最短超串
 */
public class ShortestSupersequenceLcci{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 ShortestSupersequenceLcci fun=new ShortestSupersequenceLcci();
	 	 Solution solution = fun.new Solution();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
	public int[] shortestSeq(int[] big, int[] small) {
		int n = big.length;
		int[] res = {-1, -1};
		// need：记录需要覆盖的数字及其需要的个数
		Map<Integer, Integer> need = new HashMap<>();
		// diff：记录滑动窗口一共需要覆盖的数字个数
		int minLen = n + 1, diff = 0;
		// 数据预处理：初始化需要覆盖的数字及其个数
		for (int num : small) {
			need.put(num, need.getOrDefault(num, 0) + 1);
			diff++;
		}
		// 滑动窗口：l指向窗口左边界，r指向窗口右边界
		int l = 0;
		for (int r = 0; r < n; r++) {
			// 如果当前数字在need中
			if (need.containsKey(big[r])) {
				// 减少该数字的需求计数
				int count = need.get(big[r]);
				need.put(big[r], count - 1);

				// 如果该数字的需求计数从正数变为非负数，说明满足了一个需求
				if (count > 0) {
					diff--;
				}
			}

			// 当所有需求都满足时，尝试收缩左边界
			while (diff == 0) {
				// 更新最小窗口
				if (r - l + 1 < minLen) {
					minLen = r - l + 1;
					res = new int[]{l, r};
				}

				// 如果左边界数字在need中
				if (need.containsKey(big[l])) {
					int count = need.get(big[l]);
					need.put(big[l], count + 1);

					// 如果该数字的需求计数从0变为正数，说明缺少了一个需求
					if (count == 0) {
						diff++;
					}
				}
				l++;
			}
		}

		return res[0] == -1 ? new int[]{} : res;

	}
}
//leetcode submit region end(Prohibit modification and deletion)

}
